package 单链表;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 姚东名
 * Date: 2024-08-27
 * Time: 21:11
 */
public class Test {
    public static void main(String[] args) {
        MySingleList mySingleList = new MySingleList();
        mySingleList.addLast(100);
        mySingleList.addLast(110);
        mySingleList.addLast(120);
        mySingleList.addLast(130);
        mySingleList.addLast(140);

        mySingleList.createLoop();
        System.out.println(mySingleList.hasCycle());

        MySingleList.ListNode ret = mySingleList.detectCycle();
        System.out.println(ret.val);
    }
    //输入两个链表，找出它们的第一个公共结点
    public static MySingleList.ListNode getIntersectionNode(MySingleList.ListNode headA,
                                                     MySingleList.ListNode headB) {
        MySingleList.ListNode pl = headA;
        MySingleList.ListNode ps = headB;
        //遍历链表，求出二者的长度：
        int lenA = 0;
        int lenB = 0;
        while (pl != null) {
            lenA++;
            pl = pl.next;
        }
        while (ps != null) {
            lenB++;
            ps = ps.next;
        }
        pl = headA;
        ps = headB;
        //求出二者长度的差值，让长链表 走他们的差值：
        int len = lenA - lenB;
        while (len < 0) {
            //证明B中的长度比A中的长度要长
            pl = headB;
            ps = headA;
            len = lenB - lenA;
        }
        //走到这 证明pl就是长链表
        while (len > 0) {
            pl = pl.next;
            len--;
        }
        while (pl != ps) {
            pl = pl.next;
            ps = ps.next;
        }
        if (pl == null) {
            return null;//不相交
        }
        return pl;
    }

    private static void createCut(MySingleList.ListNode headA,
                                  MySingleList.ListNode headB) {
        headB.next.next.next = headA.next.next;
    }
    public static void main5(String[] args) {
        MySingleList mySingleList = new MySingleList();
        mySingleList.addLast(100);
        mySingleList.addLast(110);
        mySingleList.addLast(120);
        mySingleList.addLast(130);
        mySingleList.addLast(140);

        MySingleList mySingleList1 = new MySingleList();
        mySingleList1.addLast(105);
        mySingleList1.addLast(115);
        mySingleList1.addLast(125);
        mySingleList1.addLast(135);
        mySingleList1.addLast(145);
        mySingleList1.addLast(199);

        createCut(mySingleList.head, mySingleList1.head);
        MySingleList.ListNode ret = getIntersectionNode(mySingleList.head, mySingleList1.head);
        System.out.println(ret.val);
    }
    public static MySingleList.ListNode mergeTwoLists(MySingleList.ListNode list1,
                                                      MySingleList.ListNode list2) {
        MySingleList.ListNode newHead = new MySingleList.ListNode(-1);
        MySingleList.ListNode tmp = newHead;

        while (list1 != null && list2 != null) {
            if (list1.val > list2.val) {
                tmp.next = list2;
                list2 = list2.next;
                tmp = tmp.next;
            } else {
                tmp.next = list1;
                list1 = list1.next;
                tmp = tmp.next;
            }
        }
        if (list1 == null) {
            tmp.next = list2;
        }
        if (list2 == null) {
            tmp.next = list1;
        }
        return newHead.next;
    }
    public static void main4(String[] args) {
        MySingleList mySingleList = new MySingleList();
        mySingleList.addLast(100);
        mySingleList.addLast(110);
        mySingleList.addLast(120);
        mySingleList.addLast(130);
        mySingleList.addLast(140);
        mySingleList.display();

        MySingleList mySingleList1 = new MySingleList();
        mySingleList1.addLast(105);
        mySingleList1.addLast(115);
        mySingleList1.addLast(125);
        mySingleList1.addLast(135);
        mySingleList1.addLast(145);
        mySingleList1.display();

        MySingleList.ListNode ret = mergeTwoLists(mySingleList.head, mySingleList1.head);
        mySingleList1.display2(ret);
    }
    public static void main3(String[] args) {
        MySingleList mySingleList = new MySingleList();
        mySingleList.addLast(10);
        mySingleList.addLast(11);
        mySingleList.addLast(12);
        mySingleList.addLast(13);
        mySingleList.addLast(14);
        mySingleList.display();

        System.out.println(mySingleList.kthToLast(10));

        /*MySingleList.ListNode ret = mySingleList.middleNode();
        System.out.println(ret.val);*/

        /*MySingleList.ListNode ret = mySingleList.reverseList();
        mySingleList.display2(ret);*/
    }
    public static void main2(String[] args) {
        MySingleList mySingleList = new MySingleList();

        mySingleList.addLast(11);
        mySingleList.addLast(11);
        mySingleList.addLast(15);
        mySingleList.addLast(14);
        mySingleList.addLast(15);

        mySingleList.removeAllKey(15);
        mySingleList.display();


        mySingleList.clear();

        /*mySingleList.display();

        mySingleList.addIndex(3, 100);

        mySingleList.display();

        mySingleList.remove(100);*/

        /*mySingleList.addFirst(11);
        mySingleList.addFirst(12);
        mySingleList.addFirst(13);
        mySingleList.addFirst(14);
        mySingleList.addFirst(15);*/
        mySingleList.display();
    }
    public static void main1(String[] args) {
        MySingleList mySingleList = new MySingleList();
        mySingleList.createList();
        mySingleList.display();
        System.out.println(mySingleList.size());
        System.out.println(mySingleList.contains(60));
    }
}
